var insertionSortList = function (head) {
    if (!head.next) return head;
    let node = head;
    const arr = [];
    while (node) {
        if (head === node) {
            arr.push(node);
            node = node.next;
            arr[0].next = null;
            console.log(arr);
            continue;
        }
        for (let i = arr.length - 1; i >= 0; i--) {
            if (arr[i].val <= node.val) {
                arr[i].next = node;
                arr.splice(i + 1, 0, node)
                node = node.next;
                if (arr[i + 2]) {
                    arr[i + 1].next = arr[i + 2];
                } else {
                    arr[i + 1].next = null;
                }
                break;
            } else if (i === 0) {
                arr.unshift(node);
                node = node.next;
                arr[0].next = arr[1];
                break;
            }
        }
    }
    return arr;
};
//[4,2,1,3]
// 测试数据
let head = {
    val: 4,
    next: {
        val: 2,
        next: {
            val: 1,
            next: {
                val: 3,
                next: null
            }
        }
    }
}
// 测试
let res = insertionSortList(head);

console.log(res);



